Math
Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin.
Math
> Number theory
> Integers
Integers
Properties of the integers.Sibling topics:
Contents:
- Linear Diophantine non-solutions
- Linear Diophantine non-solutions 2
- Definition of a linear Diophantine equation
- Definition of relatively prime
Definition of a linear Diophantine equation
A linear Diophantine equation is an equation of the form `ax+by=c`, where all variables are integers.
Definition of relatively prime
Two numbers `x` and `y` are relatively prime means:
GCD(x,y)=1
Theorem: Linear Diophantine non-solutions
Given `a,b,c,d in ZZ`, if `d div a` and `d div b` and `d !div c`, then the equation
`ax+by=c` has no integer solution for `x` and `y`.
Proof:
Assume by way of contradiction that the equation does have an integer solution. Then by
Divisor divides multiples we know that `d div ax and d div by`, and by Divisor of a sum,
we know that `d div (ax+by)`, which means that `d div c`.
However, we've stated that `d !div c`, so that is impossible. Therefore, the equation has no solutions.
Corollary (of
Linear Diophantine non-solutions):
Linear Diophantine non-solutions 2
Given `a,b,c in ZZ` with `a` and `b` not both equal to zero, and `d=GCD(a,b)`. If the diophantine equation
`ax+by=c` has an integer solution for `x` and `y`, then `d div c`. (Note that this is not the same as saying
"If `d div c`, then the equation has a solution.)
Proof:
We'll prove this by proving the contrapositive: if `d !div c`, then the diophantine equation has no solutions.
Because `d=GCD(a,b)`, `d div a and d div b` by
the definition of
GCD, and by applying
Linear Diophantine non-solutions, we can see that the equation has no solutions.